package xyz.naokeziteng.sort;

import java.util.Arrays;

/**
 * @author hawk
 * @date 2022/8/15
 * @desc 归并排序
 **/
public class MergeSort2 {

    //arr[l,r)
    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r - 1) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid, r);
        merge(arr, l, mid, r);
    }

    //arr[l,mid),arr[mid,r)
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] aux = Arrays.copyOfRange(arr, l, r);
        int i = l;
        int j = mid;
        for (int k = l; k < r; k++) {
            if (i >= mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j >= r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6, 2, 4, 7, 8};
        mergeSort(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
    }
}
